package com.github.hgkmail.hello.leetcode101.collection.array;

//从右上角或左下角开始搜索，一个方向是增大，一个方向是减小
//二维数组坐标系：i->行，j->列，注意和笛卡尔坐标系不一样！
// (0,0) (0,1) (0,j)
// (1,0)
// (i,0)       (i,j)
//两条对角线：i-j，i+j
public class LC240SearchA2dMatrix2 {
    //右上角
    public boolean searchMatrix1(int[][] matrix, int target) {
        int m=matrix.length;
        int n=matrix[0].length;
        if (m<=0 || n<=0) {
            return false;
        }
        int i=0;
        int j=n-1;
        while (i<m && j>=0) {
            if (matrix[i][j]==target) {
                return true;
            } else if (matrix[i][j]>target) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }

    //左下角
    public boolean searchMatrix2(int[][] matrix, int target) {
        int m=matrix.length;
        int n=matrix[0].length;
        if (m<=0 || n<=0) {
            return false;
        }
        int i=m-1;
        int j=0;
        while (i>=0 && j<n) {
            if (matrix[i][j]==target) {
                return true;
            } else if (matrix[i][j]>target) {
                i--;
            } else {
                j++;
            }
        }
        return false;
    }

    public static void main(String[] args) {

    }
}
